\section{回溯与搜索}
求解回溯问题的常见原则：
\begin{itemize}
	\item 找到停止条件。
	\item 子问题可解。
\end{itemize}
通常我们递归搜索可行解的时候我们可能会找到错误的结果，当找到错误的结果之后应该尝试其他的路线。但是这时候可能出现我们找到错误结果的时候已经修改了当前的访问状态。如果后面回退之后没有修改错误的访问状态会导致错误。
\subsection{数的次方}
\begin{example}[变量a的n次方]
	\begin{equation}
		a^n =
		\begin{cases}
			 & a^{\frac{n}{2}}\cdot a^{\frac{n}{2}}       \\
			 & a^{\frac{n-1}{2}}\cdot a^{\frac{n-1}{2}}*a
		\end{cases}
	\end{equation}
\end{example}
\begin{longlisting}
	\caption{数的n次方}
	\cppfile[firstline=2,lastline=11]{third_party/coding/cxx/algorithm/recursion/src/power_n.cc}
	\label{code:powN}
\end{longlisting}
\subsection{N皇后问题}
\begin{example}[N皇后问题]
	N皇后问题是一个以国际象棋为背景的问题，以N=8为例，如何能够在$8\times 8$的国际象棋棋盘上放置8个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？国际象棋中任两个皇后都不能处于同一条行、列、正斜线或反斜线上。(当且仅当n = 1或$n \geq 4$时问题有解)。
\end{example}
\begin{Mind}{N皇后问题}{}
	对于N皇后的棋盘，从第一行开始放置，然后在列中选择一个位置。如果此位置是合法的，则将其作为下次递归的起点，直到递归到最后一行也合法（r==N）。
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includesvg[width=\textwidth]{queen_8}
	\caption{8皇后问题}
	\label{fig:chessboard}
\end{figure}
\begin{longlisting}
	\caption{n皇后问题总共摆法}
	\cudafile[firstline=26,lastline=49]{third_party/coding/cxx/algorithm/backtrack/src/n_queue.cc}
	\label{code:n_queue}
\end{longlisting}
\subsection{字符串的全排列}
\begin{Mind}{全排列思路}{}	对于abc字符串中的每一位，依次交换其和剩余字符串的位置。例如abc第一位和a、第二位b、第三位c交换分别为abc、bac、cba。对于交换之后的部分假定已经全部排列好了。例如bc全排列好了应该是bc和cb。那第一次分割a和bc的这一组结果就是abc和acb。同理其它的也可以按照这个来，分别即可得到bac和bca以及cba和cab。对于bc应该怎么排列？同样按照第一位和剩余位交换分为b和c以及c和b。对于剩下的c按照同样的方式分割。但是因为c已经没有后续字母了，它的排列为c，示意图入\figref{fig:permutation}。由此可知算法为：将字符串的每一位分别和后面的每一位交换。这样交换的后半部分长度将少1（少了第一位），对于这个字串做同样的操作指导字串长度为1（不可分割）则结束分割。因此递归结束的条件是当前需要分割的字符串k（位置k）已经达到字符串末尾（length(str)-1）。还有一个问题是交换后需要交换回来，比如abc中a和第二位交换变成了bac。假设ac排好了（good(ac)）轮到cba这组操作的字符串递归操作的时候字符串已经由原来的abc变成了bac。无疑这样将导致后续交换出问题。所以当b(good(ac))后需要将其换回abc。
\end{Mind}
\begin{longlisting}
	\caption{字符串的全排列}
	\cppfile[firstline=6,lastline=24]{third_party/coding/cxx/algorithm/common/src/permutation.cc}
	\label{code:strPermutation}
\end{longlisting}
\begin{figure}
	\begin{center}
		\includegraphics[width=0.6\textwidth]{permutation}
	\end{center}
	\caption{全排列算法}
	\label{fig:permutation}
\end{figure}

\subsection{迷宫}
\figref{fig:maze} 初始位置在m，m的位置(3,3)进栈，上下左右查找能走的方向，发现(2 3),(3 2)能走，于是将其压栈(b)。当前位置设置为栈顶元素(3 2)同时查找能走的方向，找到(2 2)和(3 1)压栈，依次直到找到目标e（h）,找到目标退出。
\begin{figure}
\centering
\includegraphics[width=\textwidth]{maze}
\caption{迷宫示意图}
\label{fig:maze}
\end{figure}
\subsection{辗转相除法求最大公约数}
\begin{algorithm}
	\caption{辗转相除法求最大公约数}
	\label{al:al1}
	\begin{algorithmic}
		\REQUIRE $a>b$
		\WHILE{$b\neq0 $}
		\STATE $a = b,b\qquad mod\qquad r$
		\ENDWHILE
	\end{algorithmic}
\end{algorithm}
\begin{longlisting}
	\caption{最大公约数}
	\cppfile[firstline=5,lastline=12]{third_party/coding/cxx/algorithm/common/src/gcd.cc}
	\label{code:gcd}
\end{longlisting}
\subsection{电话号码的字母组合}
\begin{Textcode}
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
\end{Textcode}
数字和字母对应关系：
\begin{itemize}
	\item 2:abc
	\item 3:def
	\item 4:ghi
	\item 5:jkl
	\item 6:mno
	\item 7:pqrs
	\item 8:tuv
	\item 9:wxyz
\end{itemize}
\begin{Mind}{DFS搜索实现}{}
	对于23的情况，假设根节点2，其对应的元素为a，b，c。而每个节点均可以到达3对应的d，e，f。如\figref{fig:letterCombinations}本质上是对这个图中的节点进行深度优先搜索。深度优先搜索也采用了递归实现（\coderef{code:letterCombinations}）和栈实现（\coderef{code:letterCombinationsDs}）。
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=.5\textwidth]{letterCombinations}
	\caption{电话号码的字母组合}
	\label{fig:letterCombinations}
\end{figure}
\begin{longlisting}
	\caption{电话号码的字母组合（递归实现）}
	\cppfile[firstline=4,lastline=29]{third_party/coding/cxx/algorithm/backtrack/src/letterCombinations.cc}
	\label{code:letterCombinations}
\end{longlisting}

\begin{longlisting}
	\caption{电话号码的字母组合（栈实现）}
	\cppfile[firstline=31,lastline=62]{third_party/coding/cxx/algorithm/backtrack/src/letterCombinations.cc}
	\label{code:letterCombinationsDs}
\end{longlisting}
% \subsection{组合总和}
% \begin{example}{组合总和}
% 给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。

% candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。 

% 对于给定的输入，保证和为 target 的不同组合数少于 150 个。

% 示例 1：

% 输入：candidates = [2,3,6,7], target = 7
% 输出：[[2,2,3],[7]]
% 解释：
% 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
% 7 也是一个候选， 7 = 7 。
% 仅有这两种组合。
% 示例 2：

% 输入: candidates = [2,3,5], target = 8
% 输出: [[2,2,2,2],[2,3,3],[3,5]]

% 示例 3：

% 输入: candidates = [2], target = 1
% 输出: []
% \end{example}
% \begin{Mind}{组合总和}{}
% 	同样是使用DFS，我们需要先确定退出条件。如果我们已经找到了对应的组合数则返回。而如果我们遍历的数字已经大于target则直接返回。只有在遍历元素小于目标的时候才应该递归调用。如果以[2,3,6,7]为例:如果我们找到了2则下一步的目标是在candidates中找到和为5的组合，如果继续递归查找，先找到了2，则下一步的目标是找到3，如此反复。于是我们得到2+2+3的组合。事实上我们在2+2这个组合下，还应该遍历所有的元素，其中6，7应该也需要纳入考虑。比如2+2+6>7这条路不通，2+2+7>7这条路也不通。所以并不是每条路都应该走，需要减枝。减枝的条件是如果我们当前元素和和所选元素和>target则不用考虑当前元素。以2为节点的路线遍历完之后，我们尝试以3为节点继续尝试，这时候3可以选择2，3，6，7。因为3+6和3+7大于目标。所以不用选择，实际上可选为2和3。这里我们应该放弃2则个选项。因为我们会得到[3,2,2]这个选项，其本质上和以2为节点的[2,2,3]是一样的。如何减去这个分支？我们可以要求加入的节点$\geq$已经加入的节点。于是我们的减枝条件有两个。至于如何当前选择的元素和究竟有没有达到target，我们有两种做法：
% 	\begin{itemize}
% 		\item 实时计算当前选中元素的和。
% 		\item 通过一个变量记录当前选中元素的和。
% 	\end{itemize}
% 	这里为了减少计算，我们直接选择记录元素的和。
% \end{Mind}
% \begin{longlisting}
% 	\caption{组合总和}
% 	\cudafile[firstline=3,lastline=32]{third_party/coding/cxx/algorithm/backtrack/src/combinationSum.cc}
% 	\label{code:combinationSum}
% \end{longlisting}

\subsection{打开旋转锁}
\begin{example}{}{打开旋转锁}
一个密码锁由 4 个环形拨轮组成，每个拨轮都有 10 个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，请给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。
\end{example}
\begin{Mind}{}
用BFS搜索+剪枝，如\figref{fig:bfs_unlock}从{0000}开始，因为每个位置可以上下变动，所有可能变动的数量是8个，即从0000能到达的状态有8种（相邻节点）。
\begin{enumerate}
	\item 如果target就在deadend中则无法打开，返回-1。
	\item 如果初始状态"0000"在deadend中则无法打开，返回-1。
	\item 如果直接BFS剪枝，剪枝条件为节点字符串"xxxx"不在deadends中，而且不在已经遍历过的节点中。
\end{enumerate}
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includegraphics*[width=0.6\textwidth]{bfs_unlock}
	\caption{初始节点搜索}
	\label{fig:bfs_unlock}
\end{figure}
\begin{longlisting}
	\caption{打开旋转锁}
	\cppfile[firstline=19,lastline=47]{third_party/coding/cxx/algorithm/backtrack/src/openLock.cc}
	\label{code:openLock}
\end{longlisting}
\subsection{机器人的移动范围}
在 m 行 n 列的格子阵列中查找能走过的格子，要求格子坐标的x，y的位数和小于指定的 k 。(例如，m=5,n=5,k=18,能访问25个格子数)。
\begin{Mind}{机器人的移动范围}{}
	这里需要注意的是，移动的过程中规则说明是可以上下左右移动，但是实际上不需要上下左右，只有在网格中间遍历所有网格的时候才需要上下左右，而从左上角[0,0]通过向下或者向右走即可走完所有的网格，走到网格中间的过程中此网格的上面和左面已经走过，所以只需要考虑从每个网格往下和往右边走即可。
\end{Mind}
\begin{figure}[!htbp]
	\centering
	\includegraphics[width=0.7\textwidth]{movingCount}
	\caption{[0,0]为起点搜索}
	\label{fig:movingCount}
\end{figure}
如\figref{fig:movingCount}，m=4，n=6，k=7，我们只能找到右下角位置索引和为8>k，所以能到达的最大位置数为23。实现如\coderef{code:movingCount}。
\begin{longlisting}
	\caption{机器人的移动范围（DFS）}
	\cppfile[firstline=40,lastline=57]{third_party/coding/cxx/algorithm/backtrack/src/movingCount.cc}
	\label{code:movingCount}
\end{longlisting}
\begin{enumerate}
	\item 时间复杂度O(mn)。
	\item 空间复杂度O(mn)。
\end{enumerate}
\subsection{岛屿的数量}
\begin{Textcode}
	给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
	输入：grid = [
	["1","1","1","1","0"],
	["1","1","0","1","0"],
	["1","1","0","0","0"],
	["0","0","0","0","0"]
	]
	输出：1
\end{Textcode}
\begin{Mind}{岛屿的数量}{}
	和机器人移动范围类似，同样采用递归搜索。不同在于岛屿数量首先需要先找到陆地，这就意味着移动的时候需要上下左右移动而不是向下或者向右。这里visited使用grid数组，如果为1则表示当前可以访问，访问后置为0表示其已经访问过了。反例如\figref{fig:numIslands}，因为起始位置的不确定，如果只按照下、右方向搜索会错过发现起点但起点坐上依然可以访问的情况。
\end{Mind}
\begin{figure}[!htbp]
	\begin{center}
		\includegraphics[width=0.5\textwidth]{numIslands}
	\end{center}
	\caption{岛屿数量搜索}
	\label{fig:numIslands}
\end{figure}

\begin{longlisting}
	\caption{岛屿的数量（DFS）}
	\cppfile[firstline=3,lastline=32]{third_party/coding/cxx/algorithm/backtrack/src/numIslands.cc}
	\label{code:numIslands}
\end{longlisting}

\begin{enumerate}
	\item 时间复杂度O(mn)。
	\item 空间复杂度O(mn)。
\end{enumerate}
\subsection{朋友圈问题}
\begin{example}
	班上有 N 名学生。其中有些人是朋友，有些则不是。它们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。给定一个 $N \times N$ 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
	\textbf{示例：}
	\begin{Textcode}
		输入:
		[[1,1,0],
		[1,1,0],
		[0,0,1]]
		输出: 2
		说明：已知学生0和学生1互为朋友，它们在一个朋友圈。
		第2个学生自己在一个朋友圈。所以返回2。
	\end{Textcode}
	\textbf{注意：}
	\begin{itemize}
		\item N 在[1,200]的范围内。
		\item 对于所有学生，有M[i][i] = 1。
		\item 如果有M[i][j] = 1，则有M[j][i] = 1。
	\end{itemize}
\end{example}
\begin{Mind}{朋友圈问题}{}
N名学生，声明一个长度为N的visited向量。从第1名学生（代码中索引为0）开始，如果当前学生没有访问过则以它作为起点访问它能到达的其他朋友（isConnected[c]==1）。然后如此递归查找直到找不到朋友为止。朋友圈+1。然后找下一个学生依次如此。
\end{Mind}
\begin{longlisting}
	\caption{朋友圈问题}
	\cudafile[firstline=4,lastline=28]{third_party/coding/cxx/algorithm/backtrack/src/findCircleNum.cc}
	\label{code:findCircleNum}
\end{longlisting}
\subsection{找出数组中和等于m的结果}
\begin{example}
	输入数字n，m，在1-n之间找出数使得它们的和等于m。以m=n=5为例子说明：任务是在1-5之间找到能求和得到5的数字。1+4或者2+3都可以满足要求。
\end{example}
\begin{Mind}{找出数组中和为m的所有结果}{}
深搜+减枝。
\end{Mind}
假设我们找到了1,那剩下的任务是在2-5之间找到数组使得和为4。此时假设选择2,剩下的任务是在3-5之间选择求和结果为2的数，但是明显没有这样的结果，于是2是不合适的。说明选择2的时候就不对，退回选择3。接下来的任务是在4-5之间选择数使得能求和等于1,显然也不满足条件，说明3也不合适，选择4。剩下的任务是在接下来的任务是在0个可选的值中选择数，于是直接输出结果。接下来2入栈，剩下的任务是从3-5中选择能得到3的数，于是选中3,接下来是3入栈，剩下的任务是在4-5中选择2,不可能，于是3出栈，4也是这样直到结束。
\begin{longlisting}
	\caption{数组中和为m的结果}
	\cudafile[firstline=4,lastline=44]{third_party/coding/cxx/algorithm/backtrack/src/findTargetFromN.cc}
	\label{code:findTargetFromN}
\end{longlisting}

\subsection{括号生成}
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。示例 1：
\begin{Textcode}
	输入：n = 3
	输出：["((()))","(()())","(())()","()(())","()()()"]
\end{Textcode}
\begin{Mind}{括号生成}{}
	使用左右括号填充长度为$2\times n$的字符串，确保左右括号能匹配。只是匹配的时候需要验证是否是有效括号组合。生成的合法括号有一下几种条件：
	\begin{enumerate}
		\item 保证左括号数和右括号数相等且为n
		\item 一定是'('先出现
		\item 左括号的数目和右括号数目相同
	\end{enumerate}
\end{Mind}

\begin{figure}[!htbp]
	\begin{center}
		\includegraphics[width=0.95\textwidth]{generateParenthesis}
	\end{center}
	\caption{括号生成DFS示意图（n=2）}
	\label{fig:generateParenthesis}
\end{figure}
上\figref{fig:generateParenthesis}可以看出，对于')'开头的根本不用匹配，肯定无效。我们可以总结：
\begin{enumerate}
	\item 起点不能以')'开头，所以dfs之前一定要保证以'('开头（函数调用先调用'('）。
	\item left不能超过n（生成对应对数的括号）。
	\item left不能超过right（文字算法中第2条）。
	\item left和right都等于n的时候找到结果（退出条件）。
\end{enumerate}
代码实现如：\coderef{code:generateParenthesis}。其中void dfsParenthesis(sys, left,right, n,cache) 表示以sys作为初始字符串，left表示'('能出现的索引开始位置，right表示')'出现的开始索引位置，直到满足n后将括号加入cache。
\begin{longlisting}
	\caption{匹配的括号}
	\cppfile[firstline=3,lastline=q9]{third_party/coding/cxx/algorithm/common/src/generateParenthesis.cc}
	\label{code:generateParenthesis}
\end{longlisting}
\subsection{打印最大的n位数}
打印从1到n位最大数的数，比如n=1则打印1-9。n=2则打印1-99。
\begin{Mind}{打印最大的n位数}{}
	数据的位数为n位。我们可以将n位数据的分为首位和其他位。比如190表示首位是1，其他位为90。我们循环遍历首位，将1-9加入结果，接着遍历第二位将1-9和第二位0-9的结果拼接在一起加入结果直到最终完成添加为止。
\end{Mind}
\begin{longlisting}
	\caption{打印1到\textbf{n位最大数}之间的所有数据}
	\cppfile[firstline=3,lastline=23]{third_party/coding/cxx/algorithm/backtrack/src/printNumbers.cc}
	\label{code:printNumbers}
\end{longlisting}
\coderef{code:printNumbers} 中numDfs(k, n, s,res)主要是为了找到第k位开始到第n位的所有数字组成的字符串，最后将结果存放到字符串向量中返回。
\subsection{组合总和}
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
\begin{Textcode}
	输入：candidates = [2,3,6,7], target = 7
	输出：[[2,2,3],[7]]
	解释：
	2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
	7 也是一个候选， 7 = 7 。
	仅有这两种组合。
\end{Textcode}
\begin{Mind}{深搜}{}
	对于target，分别减去candidates，如果元素小于0则此路径继续计算会导致越来越小于0，所以直接删除。所以此问题变成了在每个节点一次减去candidates的元素直到找到跟节点0为止。
	需要注意的是223和232分别都能得到结果，但是选择223。也就是说加入节点的时候需要再做一次判断保证加入的节点得到值不能小于之前的值。如\figref{fig:combinationSum}。
\end{Mind}
\begin{figure}[!htbp]
	\begin{center}
		\includegraphics[width=0.95\textwidth]{combinationSum}
	\end{center}
	\caption{组合数的路径}
	\label{fig:combinationSum}
\end{figure}
实现如：
\begin{longlisting}
	\caption{组合总和}
	\cppfile[firstline=3,lastline=32]{third_party/coding/cxx/algorithm/backtrack/src/combinationSum.cc}
	\label{code:combinationSum}
\end{longlisting}
\subsection{组合总和II}
给定一个候选人编号的集合candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。candidates中的每个数字在每个组合中只能使用一次。注意：解集不能包含重复的组合。
\begin{Textcode}
	输入: candidates = [10,1,2,7,6,1,5], target = 8,
	输出:
	[
	[1,1,6],
	[1,2,5],
	[1,7],
	[2,6]
	]
\end{Textcode}
\begin{Mind}{组合总和II}{}
	设置起点从起点往后搜索。不同在于剪枝，如\figref{fig:combinationSum2}，首先必须是在起点之后搜索（i>start），然后就是候选值不能大于当前搜索值（target - candidates[i] >= 0），更重要的一点同一层不能有重复节点。
\end{Mind}
\begin{figure}
	\begin{center}
		\includegraphics[width=0.95\textwidth]{combinationSum2}
	\end{center}
	\caption{组合总和}
	\label{fig:combinationSum2}
\end{figure}

\begin{longlisting}
	\caption{组合总和II}
	\cppfile[firstline=34,lastline=58]{third_party/coding/cxx/algorithm/backtrack/src/combinationSum.cc}
	\label{code:combinationSum2}
\end{longlisting}
如\figref{fig:combinationSum2}，排序后的结果中右两个1，第一层选择第一个1和第二个1本质上会生成相同的节点，所以保证i>start的时候，此层节点1已经生成，那么candidates[i]==candidates[i-1]的这个1实际上有没有存在的必要了。

\subsection{\href{https://leetcode.cn/problems/subsets/description/}{子集}}
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
\begin{Textcode}
	输入：nums = [1,2,3]
	输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
\end{Textcode}
\begin{Mind}{子集}{}
	通过0表示不选中，1表示选中。三个位置则有3!中选项，通过此规则过滤数据即可实现。
\end{Mind}
\begin{table}[H]
	\caption{子集}
	\centering
	\begin{tabular}{ccc}
		\toprule
		mask & 数值 & 选中元素    \\
		\midrule
		000  & 0  & []      \\
		001  & 1  & [3]     \\
		010  & 2  & [2]     \\
		011  & 3  & [2,3]   \\
		100  & 4  & [1]     \\
		101  & 5  & [1,3]   \\
		110  & 6  & [1,2]   \\
		111  & 7  & [1,2,3] \\
		\bottomrule
	\end{tabular}
\end{table}
值得注意的是，二进制和数据的相互选择。对已一个元素为3的情况，对应的二进制值为0-7。所以我们循环遍历这8个元素分别找到对应位置为1的结果。例如110（6）。我们需要获取nums的1和2。其索引分别为0，1。我们可以使用这个数字num \&(1>>k)(k=0,1,2)这样可以把两个1所在的位置k拿到（这里索引为0、1或者是1、0无非是结果为12或者23的差别）因为是子集，无顺序要求，所以可以随便处理。
\begin{longlisting}
	\caption{子集}
	\cppfile[firstline=3,lastline=17]{third_party/coding/cxx/algorithm/backtrack/src/subsets.cc}
	\label{code:subsets}
\end{longlisting}
\begin{itemize}
	\item 时间复杂度：$O(n\times 2^n)$。
	\item 空间复杂度：$O(n)$。
\end{itemize}
\subsection{单词搜索}
\begin{example}[单词搜索]
给定一个 $m\times n$ 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

	输入:

	board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"

	输出:
	true
示意图如：\figref{fig:exist}
\end{example}
\begin{figure}[!htbp]
	\centering
	\includesvg[width=.5\textwidth]{exist.svg}
	\caption{单词搜索}
	\label{fig:exist}
\end{figure}
\begin{Mind}{单词搜索}{}
从board中找到第一个和word首字母相同的字符。然后在此位置上下左右查找可选结果，如果能找到下一个和word下一个字符相等的字符那么在下一个位置按照同样地规则搜索直到找到word最后一个单词即可。
\end{Mind}
\begin{longlisting}
	\caption{单词搜索}
	\cudafile[firstline=7,lastline=50]{third_party/coding/cxx/algorithm/backtrack/src/exist.cc}
	\label{code:exist}
\end{longlisting}
\subsection{\href{}{单词搜索II}}
\begin{example}[单词搜索II]
给定一个 $m \times n$ 二维字符网格 board 和一个单词（字符串）列表 words， 返回所有二维网格上的单词 。单词必须按照字母顺序，通过 相邻的单元格 内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母在一个单词中不允许被重复使用。
\end{example}
\begin{figure}
	\centering
	\includesvg[width=.5\textwidth]{findWords2}
	\caption{单词搜索II}
	\label{fig:findWords2}
\end{figure}
\begin{Mind}{单词搜索II}{}
	回溯，先找到第一个字母（此字母需要在Trie树中能找到），然后在此位置上下左右查找可选结果，反复递归找到最后，如果这个单词在结果集合中没有出现过则加入集合（使用集合的原因是可能会从多个位置找到相同的单词结果）。
\end{Mind}

\begin{longlisting}
	\caption{单词搜索II}
	\cppfile[firstline=29,lastline=57]{third_party/coding/cxx/algorithm/datastruct/src/findWords.cc}
	\label{code:wordFinds2}
\end{longlisting}
\subsection{\href{https://leetcode.cn/problems/minimum-genetic-mutation/description/?envType=study-plan-v2&envId=top-interview-150}{最小基因变化}}
\begin{example}[最小基因变化]
基因序列可以表示为一条由 8 个字符组成的字符串，其中每个字符都是 'A'、'C'、'G' 和 'T' 之一。

假设我们需要调查从基因序列 start 变为 end 所发生的基因变化。一次基因变化就意味着这个基因序列中的一个字符发生了变化。

例如，"AACCGGTT" --> "AACCGGTA" 就是一次基因变化。
另有一个基因库 bank 记录了所有有效的基因变化，只有基因库中的基因才是有效的基因序列。（变化后的基因必须位于基因库 bank 中）

给你两个基因序列 start 和 end ，以及一个基因库 bank ，请你找出并返回能够使 start 变化为 end 所需的最少变化次数。如果无法完成此基因变化，返回 -1 。

注意：起始基因序列 start 默认是有效的，但是它并不一定会出现在基因库中。

\begin{Textcode}
示例 1：

输入：start = "AACCGGTT", end = "AACCGGTA", bank = ["AACCGGTA"]
输出：1
示例 2：

输入：start = "AACCGGTT", end = "AAACGGTA", bank = ["AACCGGTA","AACCGCTA","AAACGGTA"]
输出：2
示例 3：

输入：start = "AAAAACCC", end = "AACCCCCC", bank = ["AAAACCCC","AAACCCCC","AACCCCCC"]
输出：3

\end{Textcode}
\end{example}
\begin{Mind}{最小基因变化}{}
startGene每个字符都可能发生变化，发生变化之后的基因组可能不是合法基因（不在bank中）。本质上是对其每一位突变为其它基因，然后对所有可能性找出endGene出现的位置。本质上相当于是以startGen作为根节点按照BFS搜索所有可能出现的结果，找到endGene出现的层就是最小基因变化。
\end{Mind}
\begin{longlisting}
	\caption{最小基因变化}
	\cppfile[firstline=3,lastline=40]{third_party/coding/cxx/algorithm/backtrack/src/minMutation.cc}
	\label{code:minMutation}
\end{longlisting}
\subsection{\href{https://leetcode.cn/problems/rotting-oranges/description/}{腐烂的橘子}}
\begin{example}[腐烂的橘子]
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
\begin{itemize}
	\item 值 0 代表空单元格；
	\item 值 1 代表新鲜橘子；
	\item 值 2 代表腐烂的橘子。
\end{itemize}
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
\begin{Textcode}
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个方向上。
示例 3：

输入：grid = [[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。
\end{Textcode}
\begin{figure}[!htbp]
	\centering
	\includesvg[width=\textwidth]{orangesRotting}
	\caption{腐烂的橘子示意图}
	\label{fig:orangesRotting}
\end{figure}

\end{example}
\begin{Mind}{腐烂的橘子}{}
找到所有腐烂的橘子，以其作为起点将周围的其它橘子加入进行BFS遍历。这样遍历一层相当于销耗一分钟，层就对应了耗时。因为有特殊情况所以还需要特殊判断一下：
\begin{enumerate}
	\item 遍历完成之后如果还有新鲜橘子则说明无法腐烂到它，返回-1。
	\item 遍历网格发现没有新鲜橘子则返回0。
\end{enumerate}
\end{Mind}

\begin{longlisting}
	\caption{腐烂的橘子}
	\cppfile[firstline=3,lastline=56]{third_party/coding/cxx/algorithm/backtrack/src/orangesRotting.cc}
	\label{code:orangesRotting}
\end{longlisting}

